/*
  This program is taken almost directly from the book
  Dov Bulka and David Mayhew, Efficient C++: Performance Programmijg Techniques,
  Addison-Wesley 2000, Chapter 12.
*/

#include <cstring>
#include <iostream>

class bigint {
  friend bigint operator+ (const bigint&, const bigint&);
  friend bool operator< (const bigint&, const bigint&);
public:
  bigint (const char*);
  bigint (unsigned = 0);
  bigint (const bigint&);
  bigint& operator= (const bigint&);
  bigint& operator+= (const bigint&);
  ~bigint();
  
  char* get_digits() const {
    return digits;
  }
  unsigned get_number_of_digits() const {
    return ndigits;
  }

private:
  char* digits;
  unsigned ndigits;
  unsigned size;
  bigint (const bigint&, const bigint&);
  char fetch(unsigned) const;
};

bigint::bigint (unsigned u) {
  unsigned v = u;
  for (ndigits = 1; (v/=10) > 0; ++ndigits) {
    ;
  }
  digits = new char[size = ndigits];
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] = u % 10;
    u /= 10;
  }
}

bigint::~bigint() {
  delete [] digits;
}

bigint::bigint (const char* s) {
  if (s[0] == '\0') {
    s = "0";
  }
  size = ndigits = std::strlen(s);
  digits = new char[size];
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] = s[ndigits - 1 - i] - '0';
  }
}

bigint::bigint (const bigint& copy_from) {
  size = ndigits = copy_from.ndigits;
  digits = new char[size];
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] = copy_from.digits[i];
  }
}

bigint::bigint (const bigint& left, const bigint& right) {
  size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
  digits = new char[size];
  ndigits = left.ndigits;
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] = left.digits[i];
  }
  *this += right;
}

inline
char bigint::fetch (unsigned i) const {
  return i < ndigits ? digits[i] : 0;
}

bigint& bigint::operator+= (const bigint& rhs) {
  unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);
  if (size < max) {
    char* d = new char[size = max];
    for (unsigned i = 0; i < ndigits; ++i) {
      d[i] = digits[i];
    }
    delete [] digits;
    digits = d;
  }
  while (ndigits < max) {
    digits[ndigits] = 0;
    ++ndigits;
  }
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] += rhs.fetch(i);
    if (digits[i] >= 10) {
      digits[i] -= 10;
      digits[i + 1] += 1;
    }
  }
  if (digits[ndigits - 1] == 0) {
    --ndigits;
  }
  return *this;
}

bigint& bigint::operator= (const bigint& rhs) {
  if (this == &rhs) return *this;
  ndigits = rhs.ndigits;
  if (ndigits > size) {
    delete [] digits;
    digits = new char[size = ndigits];
  }
  for (unsigned i = 0; i < ndigits; ++i) {
    digits[i] = rhs.digits[i];
  }
  return *this;
}

std::ostream& operator<< (std::ostream& os, bigint& bi) {
  char c;
  const char* d = bi.get_digits();
  for (int i = bi.get_number_of_digits() - 1; i >= 0; i--) {
    c = d[i] + '0';
    os << c;
  }
  os << std::endl;
  return os;
}

inline
bigint operator+ (const bigint& left, const bigint& right) {
  return bigint(left, right);
}

inline
bool operator< (const bigint& left, const bigint& right) {
  if (left.ndigits < right.ndigits) return true;
  if (left.ndigits > right.ndigits) return false;
  int i = left.ndigits - 1;
  for ( ; i > 0; --i) {
    if (left.digits[i] != right.digits[i]) break;
  }
  return left.digits[i] < right.digits[i];
}

#ifdef TEST_BIGINT
#define test_bigint main
#endif


#include <cassert>

int test_bigint() {

  std::cout <<"testing integer constructor" << std::endl;
  bigint a = 123;
  std::cout <<"testing character constructor" << std::endl;
  bigint b = "876";
  std::cout <<"testing operator+" << std::endl;
  bigint c = a + b;
  std::cout <<"testing operator<" << std::endl;
  assert(bigint(998) < c);
  assert(c < bigint("1000"));
  assert((bigint(999) < c) == false);
  assert((c < bigint(999)) == false);
  return 0;
}

